
\section{Problem Definition}
We target the setting of heterogeneous Web data where only little or no overlap between the schemas of the source and target instances exist. %This may be due to the lack of alignment between schemas that can be computed upfront, or because correspondences between classes simply cannot be established. 
%Without schema overlap, existing approaches \cite{juanzi_li_rimom:_2009,hu_bootstrapping_2011} that perform \emph{direct matching} between the source and target instances based on some common attributes are not applicable. As opposed to direct matching, we propose a disambiguation technique, which involves only instances of the same target dataset. In this section, we introduce the data model and then, present the problem and the main ideas behind our solution.

\newdef{definition}{Definition}  
\subsection{Preliminary}
Web data, including relational data, XML and RDF (Resource Description Framework), can be conceived as graphs. 
%For instance, tuples in the relational database setting correspond to graph nodes and foreign key relationships between them represent edges.
RDF data consist of triples, which collectively form a graph. Closely resembling this RDF data model
% (omitting special RDF semantics and constructs such as blank nodes), 
we conceive Web data as graphs: 
\begin{definition} Data model - Data on the Web are modeled as a set of graphs $\mathbb{G}$, where every graph G $\in\mathbb{G}$ is a set of triples, each of the form (s, p, o) where s $\in$U (called subject), p $\in$ U (predicate) and o $\in$ U $\cup$ L (object). Here, U denotes the set of Uniform Resource Identifiers (URIs) and L the set of literals, which together, form the vocabulary V = U $\cup$ L.  
\end{definition} 
With respect to this model, instances are resources that appear at the subject position of triples, and the attribute-value pairs of an instance $s$ correspond to the predicate-object pairs that appear in triples where $s$ is the subject (attribute and predicate are used interchangeably in the following). The representation of an (set of) instance is defined as follows:

\begin{definition} Instance Representation -The \emph{instance representation} $IR: \mathbb{G} \times 2^U \rightarrow \mathbb{G}$ is a function, which given a graph $G$ and a set of instances W, yields a set of triples in which $s \in W$ appears as the subject, i.e. $IR(G, W) = \{ (s, p, o) | (s, p, o) \in G, s \in W \}$. 
\end{definition} 

Notice that a representation of a single instance $s$ is given by $IR(G, \{s\})$. 
%We will use the terms instance and instance representation interchangeably from now on. 
For simplicity, we use in this work the outgoing edges $(s, p, o)$ of a resource $s$ to form its representation $IR(G, \{s\})$.
% However, other types of representations that may include incoming edges, as well as more complex structures in the data (e.g. paths instead of edges), are applicable. 
Based on this representation, instance matching can be posed as a \emph{direct matching problem} as follows:

\begin{definition} Instance Matches - Given two instances $s$ and $t$, from $G_s$ and $G_t$ respectively, and a similarity relation over their representations, denoted as $\sim_I$, they match if IR ($G_s$, \{s\}) $\sim_I$ IR($G_t$, \{t\}).
\end{definition}
%In this heterogeneous data setting where there is only small overlaps between the instances' schemas, we revisit this formulation of the instance matching problem to present the ideas behind our solution. 

\subsection{Solution Overview}
Our solution goes beyond this direct matching (i.e. matching an instance directly against one other) to perform an additional step of class-based disambiguation. It is based on the observation that for a collection of semantically related source instances, target matches are also semantically related among themselves.
%, i.e. target matches are related when source instances are related. 
In particular, we consider the case where resources are semantically related in the sense that together, they form a \emph{class}.  Notice, that, in this paper, a class means a set of instances that share some similar attributes. Then, the intuition behind our approach is as follows: Given source instances that belong to a particular class $C$, and a set of candidate matches, we consider candidates as correct when (1) they belong to the same class. (2) Further, because candidates should match source instances, this class must be similar to $C$. In RDF, class information may be explicitly given in the form of (s, rdf:type, o) triples, or directly derived from the data by grouping together instances that share some attributes~\cite{yongtao2011}. 

%We note that this class-based disambiguation resembles similarity flooding \cite{melnik_similarity_2002} in the sense that a class can be considered as a neighbour, and we gain more confidence that two instances match, when their class neighbours also match. 
%Thus, our approach can be seen as a particular implementation of this framework. 
%However, whereas previous works in this direction operate on one single graph, and employ neighbours that are explicitly given as nodes, our work involves multiples graphs, and computes the class representation of target instances on the fly. 
%collective inference procedure used in the artificial intelligence community \cite{jensen_why_2004} that makes joint inferences (e.g., detect a class) over multiple data instances (e.g., candidate matches) by exploiting dependencies observed in relational data.  
%There are other techniques that try to infer matches collectively, such as similarity flooding and Markov logic for instance matching. We differ from both of them because 
%However, instead of operating we infer the matches without assuming any overlap between the two graph that we want to match beside a similar identifier that the instances may share. We similarly propagate the similarity among the instances to detect correct matches; however, this process involves multiples graphs, composed in a non-trivial fashion that it is differently from the process conventionally designed in similarity flooding. Both techniques can be adapted to implement our approach; however, we decided to implement a simpler algorithm that focused on the specific problem that we have. 

We cast the instance-matching problem posed above as follows: Given a set of instances $S$ in a graph $G_s$ that belong to a class $C$ (e.g. Diseases), and for each instance $s \in S$, let the set of instances $T \in \mathbb{T}$ in a target graph $G_t$ be candidate matches. Only some of these candidates are correct matches, and based on our observation, we infer that correct matches must belong to a class similar to $C$. The problem then breaks down to (1) finding a class representation in $G_t$ that correspond to $C$, and (2) refining $\mathbb{T}$ by filtering out the instances $t \in T \in \mathbb{T}$, which do not belong to this class. 

%Thus, instance matching is actually decomposed into two sub-problems. 
%\textbf{Problem 1:} Find candidate instances for each source instance s in S. This is the direct matching problem that is addressed by existing blocking techniques.% 
%\textbf{Problem 2:} For every s, find a subset of candidate instances that represent correct matches. We call this the disambiguation problem and use class-based disambiguation to deal with that. 

We leverage existing work on blocking to deal with the first sub-problem: For each instance $s \in S$, we obtain the candidate sets $T \in \mathbb{T}$ that we call \textit{pseudo-homonym sets}: 
%Although we can solve this problem by applying the existing token-based blocking technique (that is agnostic of the schema such that no schema overlap between source and target instances are assumed) over the identifiers of the instances in $G_s$ and $G_t$, it is an approximate solution for the instance-matching problem, since pseudo-homonyms sets are ambiguous by definition. For instance, a source instance identified by the label “Anemia” may match a target instance identified by “Anemia” (a disease) and another identified by “Anemia” (a plant).
\begin{definition} Candidate Matches / Pseudo-homonym Set - Given the source dataset $G_s$, the target dataset $G_t$ and a similarity relation over the vocabulary $V$, denoted as $\sim_V$, a \emph{pseudo-homonym set} of an instance $s$ is $PH(s) = \{ s' | (s, p, o) \in G_s, (s', p', o') \in G_t, o \sim_V o'\}$.  
\end{definition}
Note that $PH(s)$ are in fact instance matches obtained via direct matching as discussed before. We explicitly introduce this notion to make clear that $PH(s)$ are only candidate matches obtained via a simple vocabulary-based matching function $\sim_V$. Further, because these matches are obtained for instances $s \in S$ of the same class $C$, we use the union set $PH(S) = \bigcup_{s \in S} PH(s)$  as an instance-based representation of the class in $G_t$ that corresponds to $C$. That is, we assume that if there exists such a class in $G_t$, it is captured by instances in $PH(S)$. Then, we filter out candidates that do not belong to this ``class'' $PH(S)$.
\begin{definition} Refined Matches - Given the instances $S$ in $G_s$ that belong to the class $C$, and $PH(S)$ the candidate matches for $S$ and the class in $G_t$ corresponding to $C$, respectively, then \emph{refined matches} are $PH'(S) = \{t| t \in PH(S), t \sim_S PH(S)\}$. 
\end{definition}
The similarity relation $\sim_S$ used here is set-based, and is for determining whether a candidate $s$ belong to the class of interest. This work is about implementing $\sim_S$ and performing the disambiguation based on it. 
